package Stack;

import java.util.LinkedList;
import java.util.Stack;

public class Test {

    //https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
    //输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。
    //例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
    //1. 0<=pushV.length == popV.length <=1000
    //2. -1000<=pushV[i]<=1000
    //3. pushV 的所有数字均不相同
    //示例1
    //输入：
    //[1,2,3,4,5],[4,5,3,2,1]
    //返回值：
    //true
    //说明：
    //可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
    //这样的顺序得到[4,5,3,2,1]这个序列，返回true
    public boolean IsPopOrder(int[] pushV,int[] popV){
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 0; i < pushV.length; i++) {
            stack.push(pushV[i]);
            while (!stack.empty() && j<popV.length && stack.peek()==popV[j]){
                stack.pop();
                j++;
            }
        }
        return stack.empty();//isEmpty()?
    }



    //https://leetcode.cn/problems/evaluate-reverse-polish-notation/
    //给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
    //请你计算该表达式。返回一个表示表达式值的整数。
    //注意：
    //有效的算符为 '+'、'-'、'*' 和 '/' 。
    //每个操作数（运算对象）都可以是一个整数或者另一个表达式。
    //两个整数之间的除法总是 向零截断 。
    //表达式中不含除零运算。
    //输入是一个根据逆波兰表示法表示的算术表达式。
    //答案及所有中间计算结果可以用 32 位 整数表示。
    //示例 1：
    //输入：tokens = ["2","1","+","3","*"]
    //输出：9
    //解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
    public int evalRPN(String[] tokens){
        Stack<Integer> stack = new Stack<>();
        for (String str : tokens) {
            if (!isOperator(str)){
                int x = Integer.parseInt((str));
                stack.push(x);
            }else{
                int val2 = stack.pop();
                int val1 = stack.pop();
                switch (str){
                    case "+":
                        stack.push(val1+val2);
                        break;
                    case "-":
                        stack.push(val1-val2);
                        break;
                    case "*":
                        stack.push(val1*val2);
                        break;
                    case "/":
                        stack.push(val1/val2);
                        break;
                }
            }
        }
        return stack.pop();
    }

    public boolean isOperator(String ch){
        if (ch.equals("+") || ch.equals("-") || ch.equals("*") || ch.equals("/")){
            return true;
        }
        return false;
    }



    //https://leetcode.cn/problems/valid-parentheses/
    //给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效
    //有效字符串需满足：
    //左括号必须用相同类型的右括号闭合。
    //左括号必须以正确的顺序闭合。
    //每个右括号都有一个对应的相同类型的左括号。
    public boolean isValid(String s){
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(ch=='(' || ch=='{' || ch=='['){
                stack.push(ch);
            }else{
                if (stack.empty()){
                    return false;
                }
                char val = stack.peek();
                if(ch==')'&&val=='(' || ch=='}'&&val=='{' || ch==']'&&val=='['){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }
        if(!stack.empty()){
            return false;
        }
        return true;
    }

    public static void main3(String[] args) {
        LinkedList<Integer> stack = new LinkedList<>();

        stack.push(12);
        stack.push(23);
        stack.push(34);
        stack.push(45);

        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.peek());
    }


    public static void main2(String[] args) {
        MyStack stack=new MyStack();
        stack.push(12);
        stack.push(23);
        stack.push(34);
        System.out.println(stack.pop());
        System.out.println(stack.pop());

    }

    public static void main1(String[] args) {
        Stack<Integer> stack=new Stack<>();
        stack.push(12);
        stack.push(23);
        stack.push(34);
        stack.push(45);

        System.out.println(stack.pop());
        System.out.println(stack.peek());
    }
}
